LeetCode 28.Implement strStr().

发表于 | 更新于 | 分类于

28.Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = “hello”, needle = “ll”

Output: 2

Example 2:

Input: haystack = “aaaaa”, needle = “bba”

Output: -1
Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().

三种解法，首先是暴力解法，本来我先写了这个解法试试看，结果leetcode没通过，在倒数第二个case时超时了，在处理aaaa…ab, aa…ab(非常多个a)这种情况时，时间复杂度时n*m，显然不是一个很好的算法，使用KMP算法只有O(n+m)。

感谢UP主 [KMP算法]NEXT数列手算演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
暴力破解法：
int strStr(char* haystack, char* needle) {
    int i = 0, j = 0, n = 0;
    if(strlen(haystack) < strlen(needle))
        return -1;
    if(strlen(needle) == 0)
        return 0;
    while(i <= strlen(haystack))
    {
        if(haystack[i] == needle[j])
            for(j = 0, n = i; j < strlen(needle) && haystack[n] == needle[j]; j++, n++)
                ;
        if(j == strlen(needle))
            return i;
        i++;
        j = 0;
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
KMP算法：
int* next_arr(char* ptr)
{
    int ptr_num = strlen(ptr);
    int* next;
    int i = 0, j = 1;
    next = calloc(ptr_num, sizeof(int));
    for(i = 1, j = 0; i < ptr_num;)
    {
        if(ptr[i] == ptr[j])
            next[i++] = ++j;
        else if(j)
            j = next[j - 1];
        else
            next[i++] = 0;
    }
    return next;
}

int strStr_kmp(char* haystack, char* needle) 
{
    int m = strlen(haystack), n = strlen(needle);
    int i, j;
    int* next = next_arr(needle);
    if (!n)
        return 0;
    for (i = 0, j = 0; i < m;)
    {
        if (haystack[i] == needle[j])
        {
            i++;
            j++;
        }
        if(j == n)
            return i - j;
        if (i < m && haystack[i] != needle[j])
        {
            if (j)
                j = next[j - 1];
            else
                 i++;
        }
    }
    free(next);
    return -1;  
}

使用KMP算法运算速率成功的打败了100%的人，然后点了
sample 0 ms submission，看到了别人的算法。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int strStr(char* haystack, char* needle) {
    int a = strlen(needle);
    int b = strlen(haystack);
    if(a==0)
        return 0;
    for(int i=0;i<b-a+1;i++){
        for(int j = 0; j<b; j++){
            if(haystack[i+j] == needle[j]){
                if(j == a-1)
                    return i;
            }
            else
                break;
        }
    }
    return -1;
}

0%